package com.my.study.algorithm.linked;

/**
 * @author Carlos
 * @version 1.0
 * @Description  链表中倒数最后k个结点
 * <p>输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
 * 如果该链表长度小于k，请返回一个长度为 0 的链表。
 *
 * 要求： 空间复杂度O(n),时间复杂度O(n)
 *       空间复杂度O(1),时间复杂度O(n)
 *
 * @date 2021/11/5 7:48
 **/
public class FindKthToTail {

    public static void main(String[] args) {
        ListNode node5 = new ListNode(5, null);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode head = new ListNode(1, node2);

        ListNode toTail = findKthToTailByForeach(head, 5);
        System.out.println(toTail);

    }



    static ListNode findKthToTailByForeach(ListNode pHead, int k) {
        // 遍历一遍链表，获取长度
        if (null == pHead) {
            return null;
        }
        int len = 0;
        ListNode temp = pHead;
        while (temp != null) {
            len++;
            temp = temp.next;
        }
        if (len < k) {
            return null;
        }
        if (len == k) {
            return pHead;
        }

        temp = pHead;
        int i = 1;

        while (i <= len - k) {
            temp = temp.next;
            i++;
        }

        return temp;
    }

    static ListNode findKthToTailByFastSlow(ListNode pHead, int k) {
        int currentIndex = 1;
        ListNode fast = pHead;
        ListNode slow = pHead;

        if (pHead == null) {
            return null;
        }

        while (currentIndex <= k && fast != null) {
            currentIndex++;
            fast = fast.next;
        }

        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        if (currentIndex <= k) {
            return null;
        }

        return slow;
    }

}
